//Quick Sort
//Chapter 7
/**
 * 对数组进行划分.
 * @param arr 目标数组
 * @param p 目标起始索引
 * @param r 目标末尾索引
 */
function Divide (arr: number[], p: number, r: number): number {
    let x = arr[r - 1];
    let i = p - 1;
    for (let j = p; j < r - 1; j++) {
        if (arr[j] < x) {
            i++;
            Swap(arr, i, j);
        }
    }
    Swap(arr, i + 1, r - 1);
    return i + 1;
}
/**
 * 交换数组中的两个元素.
 * @param arr 目标数组
 * @param a 一个元素的下标
 * @param b 另一个元素的下标
 */
function Swap (arr: number[], a: number, b: number) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}

/**
 * 快速排序,时间复杂度为Θ(n lg n).
 * @param arr 目标数组
 * @param p 目标起始索引
 * @param r 目标末尾索引
 */
function QuickSort (arr: number[], p: number, r: number) {
    if (p < r) {
        let q: number = Divide(arr, p, r);
        QuickSort(arr, p, q - 1);
        QuickSort(arr, q + 1, r);
    }
}
export { QuickSort };